翻訳と辞書 Words near each other ・ Polynomial lemniscate ・ Polynomial long division ・ Polynomial matrix ・ Polynomial regression ・ Polynomial remainder theorem ・ Polynomial representations of cyclic redundancy checks ・ Polynomial ring ・ Polynomial sequence ・ Polynomial signal processing ・ Polynomial SOS ・ Polynomial texture mapping ・ Polynomial transformations ・ Polynomial Wigner–Ville distribution ・ Polynomial-time algorithm for approximating the volume of convex bodies ・ Polynomial-time approximation scheme ・ Polynomial-time reduction ・ Polynomially reflexive space ・ Polynomiography ・ Polynoncus ・ Polynormal subgroup ・ Polynormande ・ Polynove Pole ・ Polynoxylin ・ Polynuclear ・ Polynucleobacter ・ Polynucleobacter acidiphobus ・ Polynucleobacter cosmopolitanus ・ Polynucleobacter difficilis ・ Polynucleobacter necessarius ・ Polynucleobacter rarus Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Polynomial-time reduction ： ウィキペディア英語版 Polynomial-time reduction In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine. There are several different types of polynomial-time reduction, depending on the details of how the subroutine is used. Intuitively, a polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems for those classes. ==Types of reduction== The three most common types of polynomial-time reduction, from the most to the least restrictive, are polynomial-time many-one reductions, truth-table reductions, and Turing reductions. *A polynomial-time many-one reduction from a problem ''A'' to a problem ''B'' (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem ''A'' into inputs to problem ''B'', such that the transformed problem has the same output as the original problem. An instance ''x'' of problem ''A'' can be solved by applying this transformation to produce an instance ''y'' of problem ''B'', giving ''y'' as the input to an algorithm for problem ''B'', and returning its output. Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp. A reduction of this type may be denoted by the expression $A\; \backslash le\_m^P\; B$.〔.〕 *A polynomial-time truth-table reduction from a problem ''A'' to a problem ''B'' (both decision problems) is a polynomial time algorithm for transforming inputs to problem ''A'' into a fixed number of inputs to problem ''B'', such that the output for the original problem can be expressed as a function of the outputs for ''B''. The function that maps outputs for ''B'' into the output for ''A'' must be the same for all inputs, so that it can be expressed by a truth table. A reduction of this type may be denoted by the expression $A\; \backslash le\_^P\; B$.〔.〕 *A polynomial-time Turing reduction from a problem ''A'' to a problem ''B'' is an algorithm that solves problem ''A'' using a polynomial number of calls to a subroutine for problem ''B'', and polynomial time outside of those subroutine calls. Polynomial-time Turing reductions are also known as Cook reductions, named after Stephen Cook. A reduction of this type may be denoted by the expression $A\; \backslash le\_T^P\; B$.〔 The most frequently used of these are the many-one reductions, and in some cases the phrase "polynomial-time reduction" may be used to mean a polynomial-time many-one reduction.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polynomial-time reduction」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.